package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/10 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */

public class 完全背包练习 {

    // arr中都是正数且无重复值，返回组成aim的方法数，暴力递归
    public static int ways1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }

    public static int process1(int[] arr, int index, int rest) {
        // base case
        // 当在面值数组的arr.length，此时越界，没有货币可以选择。
        // 如果当前目标金额就是0，那么存在一种方法，如果目标金额不为0，返回0中方法
        if(index == arr.length) {
            return rest == 0 ? 1 : 0 ;
        }

        // 普遍位置
        int ways = 0;
        // 从0号位置开始枚举，选择0张，1张，2张等
        // 条件是张数乘以选择的面值，不超过木匾面值rest
        for(int zhang = 0;  zhang * arr[index] <= rest ;zhang++) {
            // 方法数加上除去当前选择后所剩面额到下一位置的选择数，递归
            ways += process1(arr, index + 1, rest -  (zhang * arr[index])  );
        }
        return ways;
    }


    // ways1暴力递归，改为记忆化搜索。ways2为记忆化搜索版本
    public static int ways2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // 缓存结构，且只和index和rest有关，跟arr无关
        int[][] dp = new int[arr.length+1][aim+1];
        // 一开始所有的过程，都没有计算呢，dp二维表初始化为-1
        // dp[..][..]  = -1
        for(int i = 0 ; i < dp.length; i++) {
            for(int j = 0 ; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        // 缓存结构向下传递
        return process2(arr, 0, aim , dp);
    }

    // 如果index和rest的参数组合，是没算过的，dp[index][rest] == -1
    // 如果index和rest的参数组合，是算过的，dp[index][rest]  > - 1
    public static int process2(int[] arr,
                               int index, int rest,
                               int[][] dp) {
        if(dp[index][rest] != -1) {
            return dp[index][rest];
        }
        if(index == arr.length) {
            dp[index][rest] = rest == 0 ? 1 :0;
            return  dp[index][rest];
        }
        int ways = 0;
        for(int zhang = 0;  zhang * arr[index] <= rest ;zhang++) {
            // 返回之前加入缓存
            ways += process2(arr, index + 1, rest -  (zhang * arr[index]) , dp );
        }
        // 返回之前加入缓存
        dp[index][rest] = ways;
        return ways;
    }

    // 记忆化搜索改造为动态规划版本，ways3。
    // 如果没有枚举行为，该动态该规划为自顶向下的动态规划和记忆化搜索等效，但这题存在枚举行为。
    public static int ways3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        // dp表
        int[][] dp = new int[N + 1][aim + 1];
        // 根据递归方法，N为arr的越界位置，但是我们的dp表定义的是N+1。
        // N位置，如果aim为0，则dp[N][0] = 1;
        dp[N][0] = 1;// dp[N][1...aim] = 0;

        // 每个位置依赖自己下面的位置，那么我们从下往上循环
        for(int index = N - 1; index >= 0; index--) {
            // rest从左往右
            for(int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for(int zhang = 0;  zhang * arr[index] <= rest ;zhang++) {
                    ways += dp[index + 1] [rest -  (zhang * arr[index])];
                }
                dp[index][rest] = ways;
            }
        }
        // 最终我们需要[0,aim]位置的解
        return dp[0][aim];
    }

    // 由于存在枚举行为，我们可以进一步优化我们的动态规划。ways4是优化的动态规划
    // 根据枚举，用具体化例子来找出规律，省掉枚举
    public static int ways4(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;// dp[N][1...aim] = 0;
        for(int index = N - 1; index >= 0; index--) {
            for(int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index+1][rest];
                if(rest - arr[index] >= 0) {
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    /**
     *  完全背包
     * 定义： dp[i]  背包容量为 P的凑方法数
     * 求组合数，先遍历物品、再遍历背包
     * dp[j] += dp[j-w[i]]
     *
     *
     */
    public static int ways5(int[] arr, int aim) {
        int []dp = new int[aim+1];
        dp[0] = 1;// 凑够背包容量为0 的方法数为1
        for (int i = 0; i <arr.length ; i++) {
            for (int j = arr[i]; j <=aim; j++) {
                dp[j] += dp[j-arr[i]];
            }
//            for (int j = aim; j >=arr[i]; j--) {
//                dp[j] += dp[j-arr[i]];
//            }
        }

        System.out.println(Arrays.toString(dp));
        return dp[aim];
    }

    public static void main(String[] args) {
        int[] arr = { 5, 10,50,100 };
        int sum = 1000;
//        System.out.println(ways1(arr, sum));
//        System.out.println(ways2(arr, sum));
//        System.out.println(ways3(arr, sum));
        System.out.println(ways4(arr, sum));
        System.out.println(ways5(arr,sum));
    }

}
